package com.shm.leetcode;

/**
 * 剑指 Offer 65. 不用加减乘除做加法
 * 写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。
 *
 *
 *
 * 示例:
 *
 * 输入: a = 1, b = 1
 * 输出: 2
 *
 *
 * 提示：
 *
 * a, b 均可能是负数或 0
 * 结果不会溢出 32 位整数
 *
 * @author SHM
 */
public class Add {

    /**
     * 解题思路
     * 如果是十进制的话，我们是如何完成加法计算的？
     *
     * 15 + 12 = ？
     * 个位数和十位数的数字分别相加先不管进位的问题，
     * 2 + 5 = 7；
     * 1 + 1 = 2；
     * 所以得到结果 27。
     *
     * 计算产生进位的数字 这里有进位吗？没有，那么就是0
     * 把上面两步的结果进行相加：27 + 0 = 27；
     * 99 + 111 = ？
     * 个、十、百位 的数字分别相加先不管进位的问题：
     * 个位：9 + 1 = 0
     * 十位：9 + 1 = 0
     * 百位：0 + 1 = 1
     * 得到临时结果：100
     *
     * 计算进位的数字：
     * 1 + 9 = 10;
     * 10 + 90 = 100;
     * 得到进位结果：110
     *
     * 相加得到结果
     * 100 + 110 = 210
     * 如何用二进制完成以上的步骤？
     * 问题1： 二进制的加法利用以上的步骤可以得到正确的结果吗？
     * 12 二进制：1100
     * 15 二进制：1111
     *
     * 各位置上的数字分别相加先不管进位的问题：
     * 1100 + 1111 = 0011
     * 得到临时二进制结果：0011
     *
     * 计算进位的数字：
     * 0100 + 0100 = 1000
     * 1000 + 1000= 10000
     * 得到进位结果：11000
     *
     * 相加得到结果
     * 0011 + 11000 = 11011（十进制：27）
     * 就目前来看，是可以的。
     *
     * 问题2：第一步骤不用加法如何得到相同结果？异或
     * 异或：相同为0，相异为1
     *
     * 1100 ^ 1111 = 0011
     *
     * 问题3：第二步骤不用加法如何得到相同结果？相与，左移一位
     * 如果一个位置上的数字相遇能得到1 ，那么表示，位置上的数字都是1，然后在往左移动一位，就是步骤二 进位得到的结果
     *
     * (1100 & 1111) << 1 = 11000
     *
     * 问题4：第三步骤不用加法如何得到相同结果？其实这是个套娃
     * 第三步不用加法实现最难，因为第三步是前两步的和，还是个加法；如果不用加法，就只能不断调用前两步的步骤。
     * 我想用下面的一张图来说明：
     *
     *
     * 从上图，你大概可以看出，这个就是在不断重复第一，第二的步骤，那么退出条件是什么？
     * 其实我们可以设想一个最坏的情况，那就是，这个循环到了一个情况，会在一直循环的情况，结果依然不变？
     * 无疑，那就是，进位的结果为0的情况，所以，其实在不考虑溢位的情况下，其实最多最多就是循环32次就行,
     * 所以，一下代码已经可以得到正确的结果了。
     *
     *
     * public int add(int a, int b) {
     * 	for (int i = 0; i < 32; i++) {
     * 		int tempSum = a ^ b;
     * 		int carrySum = (a & b) << 1;
     * 		a = tempSum;
     * 		b = carrySum;
     *        }
     * 	return a;
     * }
     * 但是以上的代码依然利用了加法运算，依然不不符合题意。
     * 那么只能根据 条件 进位的结果为0的情况 进行判断停止了，就有了一下正确的代码。
     *
     * 作者：fakerleet
     * 链接：https://leetcode-cn.com/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof/solution/jin-zhi-tao-wa-ru-he-yong-wei-yun-suan-wan-cheng-j/
     * @param a
     * @param b
     * @return
     */
    public int add(int a, int b) {
        while(b != 0) {
            // 当进位为 0 时跳出
            int c = (a & b) << 1;
            // c = 进位
            a ^= b;
            // a = 非进位和
            b = c;
            // b = 进位
        }
        return a;
    }
}
